package com.dyz.leetcode._20_dynamicProgramming._198;

import java.util.Arrays;

public class _198_rob01 {
    // 记忆化搜索(一)
    public int rob(int[] nums) {
        // memo[i]：存储偷盗 [i, nums.length - 1] 区间房子得到的最大金额
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return dfs(nums, 0, memo);
    }

    private int dfs(int[] nums, int i, int[] memo) {
        if (i >= nums.length) {return 0;}

        if (memo[i] != -1) {return memo[i];}

        int left = dfs(nums, i + 1, memo);
        int right = dfs(nums, i + 2, memo);

        memo[i] = Math.max(left, right + nums[i]);
        return memo[i];
    }

}
